import java.util.Stack;

/**
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 *
 *https://leetcode.cn/problems/recover-binary-search-tree/
 * 采用中序遍历借用栈非递归
 */
class RecoverTreeDIGuiInorder {
    public void recoverTree(TreeNode root) {
        TreeNode x=null;
        TreeNode y=null;
        TreeNode pre=null;
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(pre!=null&&pre.val>root.val){
                y=root;
                if(x==null){
                    x=pre;
                }else{
                    break;
                }
            }
            pre=root;
            root=root.right;
        }
        swap(x,y);
        return;
    }
    public void swap(TreeNode x,TreeNode y){
        int tmp=x.val;
        x.val=y.val;
        y.val=tmp;
    }
}